package com.data.bobostructure.chapter2;

import com.data.bobostructure.utils.SortUtils;

/**  默认从小到大排序
 * Created by wangbing on 2018/3/31.
 */
public class QuickSort {
    private static void  quickSort(Comparable[] arr, int l,int r){
//        对arr[l……r]部分进行排序
        if (l>=r){
            return;
        }
        int p = partition(arr,l,r);
        quickSort(arr,l,p-1);
        quickSort(arr,p+1,r);
        return;

    }
//arr[l……r] 部分进行partition操作
//    返回p，使得arr[l……p-1]<arr[p] ,arr[p+1……r]> arr[p]
    private static int partition(Comparable[] arr, int l, int r) {
        int p =l;

        Comparable centerNum = arr[l];
        for (int i=l+1;i<=r;i++){
//
            if (arr[i].compareTo(centerNum)<0){
                SortUtils.swap(arr,p+1,i);
                p++;
            }
        }
//      经历过上面的排序之后  p指向的位置，是小于centerNum的，所以要交换
        SortUtils.swap(arr,l,p);
        return p;
    }

    public static void  sort(Comparable[] arr){
        quickSort(arr,0,arr.length-1);

    }

    public static void main(String[] args) {
        Comparable[] arr = SortUtils.generateRandomArray(10000000,1,10000000);
        SortUtils.testSort("com.data.structure.chapter2.QuickSort","sort",arr);
    }
}
